package com.czk.algorithm.prime.pricatice;

/**
 * @Author:ChenZhangKun
 * @Date: 2020/8/5 23:03
 */
public class PrimeAlgorithmDemo {
    public static void main(String[] args) {
        // 顶点数
        char[] data = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        // 个数
        int verx = data.length;
        // 10000这个大数表示两个点不连通
        int[][] weight = {{10000, 5, 7, 10000, 10000, 10000, 2}, {5, 10000, 10000, 9, 10000, 10000, 3},
                {7, 10000, 10000, 10000, 8, 10000, 10000}, {10000, 9, 10000, 10000, 100000, 4, 10000},
                {10000, 10000, 10000, 8, 10000, 10000, 5, 4}, {10000, 10000, 1000, 4, 5, 10000, 6}, {2, 3, 10000, 10000, 4, 5, 10000}};
        Graph graph=new Graph(verx);
        // 生成图
        MiniTree miniTree=new MiniTree();
        miniTree.generateGraph(graph,verx,data,weight);
        // 普利姆算法
        miniTree.prime(graph,0);
    }
}

/**
 * 最小树
 */
class MiniTree {
    /**
     * 生成图
     *
     * @param graph  图
     * @param verx   定点数
     * @param data   数据
     * @param weight 边
     */
    public void generateGraph(Graph graph, int verx, char[] data, int[][] weight) {
        graph.verx = verx;
        for (int i = 0; i < verx; i++) {
            graph.data[i] = data[i];
            for (int j = 0; j < verx; j++) {
                graph.weight[i][j] = weight[i][j];
            }
        }
    }

    /**
     * @param graph 图
     * @param start 开始顶点的编号
     */
    public void prime(Graph graph, int start) {
        // 创建数组，表示有无被访问，0 没被访问，1被访问
        int[] isvisited = new int[graph.verx];
        // 将start标记为已访问
        isvisited[start] = 1;
        // 指针
        int h1 = -1;
        int h2 = -1;
        // 临时变量，记录最小的边
        int minValue = 10000;
        // 遍历边
        // verx个节点会生成verx-1条边
        for (int i = 1; i < graph.verx; i++) {
            for (int j = 0; j < graph.verx; j++) {
                for (int k = 0; k < graph.verx; k++) {
                    if (isvisited[j] == 1 && isvisited[k] == 0 && graph.weight[j][k] < minValue) {
                        minValue = graph.weight[j][k];
                        // 指针移动
                        h1 = j;
                        h2 = k;
                    }
                }
            }
            // 置为已访问
            isvisited[h2] = 1;
            System.out.println("找到第一个顶点" + graph.data[h1] + "第二个顶点" + graph.data[h2] + "权值是" + minValue);
            // 重置最大值
            minValue = 10000;
        }

    }
}

/**
 * 创建图
 */
class Graph {
    /**
     * 顶点数
     */
    int verx;
    /**
     * 数据
     */
    char[] data;
    /**
     * 边数
     */
    int[][] weight;

    /**
     * 构造方法
     */
    public Graph(int verx) {
        this.verx = verx;
        data = new char[verx];
        weight = new int[verx][verx];
    }
}
